home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcl / src-16f.lha / compiler / gtn.lisp < prev    next >
Encoding:
Text File  |  1992-04-03  |  8.8 KB  |  247 lines
  1. ;;; -*- Package: C; Log: C.Log -*-
  2. ;;;
  3. ;;; **********************************************************************
  4. ;;; This code was written as part of the CMU Common Lisp project at
  5. ;;; Carnegie Mellon University, and has been placed in the public domain.
  6. ;;; If you want to use this code or any part of CMU Common Lisp, please contact
  7. ;;; Scott Fahlman or slisp-group@cs.cmu.edu.
  8. ;;;
  9. (ext:file-comment
  10.   "$Header: gtn.lisp,v 1.13 92/04/01 15:30:08 ram Exp $")
  11. ;;;
  12. ;;; **********************************************************************
  13. ;;;
  14. ;;;    This file contains the GTN pass in the compiler.  GTN allocates the TNs
  15. ;;; that hold the values of lexical variables and determines the calling
  16. ;;; conventions and passing locations used in function calls.
  17. ;;;
  18. ;;; Written by Rob MacLachlan
  19. ;;;
  20. (in-package 'c)
  21.  
  22.  
  23. ;;; GTN-Analyze  --  Interface
  24. ;;;
  25. ;;;    We make a pass over the component's environments, assigning argument
  26. ;;; passing locations and return conventions and TNs for local variables.
  27. ;;;
  28. (defun gtn-analyze (component)
  29.   (setf (component-info component) (make-ir2-component))
  30.   (let ((funs (component-lambdas component)))
  31.     (dolist (fun funs)
  32.       (assign-ir2-environment fun)
  33.       (assign-return-locations fun)
  34.       (assign-ir2-nlx-info fun)
  35.       (assign-lambda-var-tns fun nil)
  36.       (dolist (let (lambda-lets fun))
  37.     (assign-lambda-var-tns let t))))
  38.  
  39.   (undefined-value))
  40.  
  41.  
  42. ;;; Assign-Lambda-Var-TNs  --  Internal
  43. ;;;
  44. ;;;    We have to allocate the home TNs for variables before we can call
  45. ;;; Assign-IR2-Environment so that we can close over TNs that haven't had their
  46. ;;; home environment assigned yet.  Here we evaluate the DEBUG-INFO/SPEED
  47. ;;; tradeoff to determine how variables are allocated.  If SPEED is 3, then all
  48. ;;; variables are subject to lifetime analysis.  Otherwise, only Let-P
  49. ;;; variables are allocated normally, and that can be inhibited by
  50. ;;; DEBUG-INFO = 3.
  51. ;;;
  52. (defun assign-lambda-var-tns (fun let-p)
  53.   (declare (type clambda fun))
  54.   (dolist (var (lambda-vars fun))
  55.     (when (leaf-refs var)
  56.       (let* ((type (if (lambda-var-indirect var)
  57.                (backend-any-primitive-type *backend*)
  58.                (primitive-type (leaf-type var))))
  59.          (temp (make-normal-tn type))
  60.          (node (lambda-bind fun))
  61.          (res (if (or (and let-p (policy node (< debug 3)))
  62.               (policy node (= speed 3)))
  63.               temp
  64.               (environment-debug-live-tn temp
  65.                          (lambda-environment fun)))))
  66.     (setf (tn-leaf res) var)
  67.     (setf (leaf-info var) res))))
  68.   (undefined-value))
  69.  
  70.  
  71. ;;; Assign-IR2-Environment  --  Internal
  72. ;;;
  73. ;;;    Give an IR2-Environment structure to Fun.  We make the TNs which hold
  74. ;;; environment values and the old-FP/return-PC.
  75. ;;;
  76. (defun assign-ir2-environment (fun)
  77.   (declare (type clambda fun))
  78.   (let ((env (lambda-environment fun)))
  79.     (collect ((env))
  80.       (dolist (thing (environment-closure env))
  81.     (let ((ptype (etypecase thing
  82.                (lambda-var
  83.             (if (lambda-var-indirect thing)
  84.                 (backend-any-primitive-type *backend*)
  85.                 (primitive-type (leaf-type thing))))
  86.                (nlx-info (backend-any-primitive-type *backend*)))))
  87.       (env (cons thing (make-normal-tn ptype)))))
  88.  
  89.       (let ((res (make-ir2-environment
  90.           :environment (env)
  91.           :return-pc-pass (make-return-pc-passing-location
  92.                    (external-entry-point-p fun)))))
  93.     (setf (environment-info env) res)
  94.     (setf (ir2-environment-old-fp res)
  95.           (make-old-fp-save-location env))
  96.     (setf (ir2-environment-return-pc res)
  97.           (make-return-pc-save-location env)))))
  98.   
  99.   (undefined-value))
  100.  
  101.  
  102. ;;; Has-Full-Call-Use  --  Internal
  103. ;;;
  104. ;;;    Return true if Fun's result continuation is used in a TR full call.  We
  105. ;;; only consider explicit :Full calls.  It is assumed that known calls are
  106. ;;; never part of a tail-recursive loop, so we don't need to enforce
  107. ;;; tail-recursion.  In any case, we don't know which known calls will
  108. ;;; actually be full calls until after LTN.
  109. ;;;
  110. (defun has-full-call-use (fun)
  111.   (declare (type clambda fun))
  112.   (let ((return (lambda-return fun)))
  113.     (and return
  114.      (do-uses (use (return-result return) nil)
  115.        (when (and (node-tail-p use)
  116.               (basic-combination-p use)
  117.               (eq (basic-combination-kind use) :full))
  118.          (return t))))))
  119.  
  120.  
  121. ;;; Use-Standard-Returns  --  Internal
  122. ;;;
  123. ;;;    Return true if we should use the standard (unknown) return convention
  124. ;;; for a tail-set.  We use the standard return convention when:
  125. ;;; -- We must use the standard convention to preserve tail-recursion, since
  126. ;;;    the tail-set contains both an XEP and a TR full call.
  127. ;;; -- It appears to be more efficient to use the standard convention, since
  128. ;;;    there are no non-TR local calls that could benefit from a non-standard
  129. ;;;    convention.
  130. ;;;
  131. (defun use-standard-returns (tails)
  132.   (declare (type tail-set tails))
  133.   (let ((funs (tail-set-functions tails)))
  134.     (or (and (find-if #'external-entry-point-p funs)
  135.          (find-if #'has-full-call-use funs))
  136.     (block punt
  137.       (dolist (fun funs t)
  138.         (dolist (ref (leaf-refs fun))
  139.           (let* ((cont (node-cont ref))
  140.              (dest (continuation-dest cont)))
  141.         (when (and (not (node-tail-p dest))
  142.                (basic-combination-p dest)
  143.                (eq (basic-combination-fun dest) cont)
  144.                (eq (basic-combination-kind dest) :local))
  145.           (return-from punt nil)))))))))
  146.  
  147.  
  148. ;;; RETURN-VALUE-EFFICENCY-NOTE  --  Internal
  149. ;;;
  150. ;;;    If policy indicates, give an efficency note about our inability to use
  151. ;;; the known return convention.  We try to find a function in the tail set
  152. ;;; with non-constant return values to use as context.  If there is no such
  153. ;;; function, then be more vague.
  154. ;;;
  155. (defun return-value-efficency-note (tails)
  156.   (declare (type tail-set tails))
  157.   (let ((funs (tail-set-functions tails)))
  158.     (when (policy (lambda-bind (first funs)) (> (max speed space) brevity))
  159.       (dolist (fun funs
  160.            (let ((*compiler-error-context* (lambda-bind (first funs))))
  161.              (compiler-note
  162.               "Return value count mismatch prevents known return ~
  163.                from these functions:~
  164.                ~{~%  ~A~}"
  165.               (remove nil (mapcar #'leaf-name funs)))))
  166.     (let ((ret (lambda-return fun)))
  167.       (when ret
  168.         (let ((rtype (return-result-type ret)))
  169.           (multiple-value-bind (ignore count)
  170.                    (values-types rtype)
  171.         (declare (ignore ignore))
  172.         (when (eq count :unknown)
  173.           (let ((*compiler-error-context* (lambda-bind fun)))
  174.             (compiler-note
  175.              "Return type not fixed values, so can't use known return ~
  176.               convention:~%  ~S"
  177.              (type-specifier rtype)))
  178.           (return)))))))))
  179.   (undefined-value))
  180.  
  181.  
  182. ;;; Return-Info-For-Set  --  Internal
  183. ;;;
  184. ;;;    Return a Return-Info structure describing how we should return from
  185. ;;; functions in the specified tail set.  We use the unknown values convention
  186. ;;; if the number of values is unknown, or if it is a good idea for some other
  187. ;;; reason.  Otherwise we allocate passing locations for a fixed number of
  188. ;;; values.
  189. ;;;
  190. (defun return-info-for-set (tails)
  191.   (declare (type tail-set tails))
  192.   (multiple-value-bind (types count)
  193.                (values-types (tail-set-type tails))
  194.     (let ((ptypes (mapcar #'primitive-type types))
  195.       (use-standard (use-standard-returns tails)))
  196.       (when (and (eq count :unknown) (not use-standard))
  197.     (return-value-efficency-note tails))
  198.       (if (or (eq count :unknown) use-standard)
  199.       (make-return-info :kind :unknown  :count count  :types ptypes)
  200.       (make-return-info
  201.        :kind :fixed
  202.        :count count
  203.        :types ptypes
  204.        :locations (mapcar #'make-normal-tn ptypes))))))
  205.  
  206.  
  207. ;;; Assign-Return-Locations  --  Internal
  208. ;;;
  209. ;;;    If Tail-Set doesn't have any Info, then make a Return-Info for it.  If
  210. ;;; we choose a return convention other than :Unknown, and this environment is
  211. ;;; for an XEP, then break tail recursion on the XEP calls, since we must
  212. ;;; always use unknown values when returning from an XEP.
  213. ;;;
  214. (defun assign-return-locations (fun)
  215.   (declare (type clambda fun))
  216.   (let* ((tails (lambda-tail-set fun))
  217.      (returns (or (tail-set-info tails)
  218.               (setf (tail-set-info tails)
  219.                 (return-info-for-set tails))))
  220.      (return (lambda-return fun)))
  221.     (when (and return
  222.            (not (eq (return-info-kind returns) :unknown))
  223.            (external-entry-point-p fun))
  224.       (do-uses (use (return-result return))
  225.     (setf (node-tail-p use) nil))))
  226.   (undefined-value))
  227.  
  228.  
  229. ;;; Assign-IR2-NLX-Info  --  Internal
  230. ;;;
  231. ;;;   Make an IR2-NLX-Info structure for each NLX entry point recorded.  We
  232. ;;; call a VM supplied function to make the Save-SP restricted on the stack.
  233. ;;; The NLX-Entry VOP's :Force-To-Stack Save-P value doesn't do this, since the
  234. ;;; SP is an argument to the VOP, and thus isn't live afterwards.
  235. ;;;
  236. (defun assign-ir2-nlx-info (fun)
  237.   (declare (type clambda fun))
  238.   (let ((env (lambda-environment fun)))
  239.     (dolist (nlx (environment-nlx-info env))
  240.       (setf (nlx-info-info nlx)
  241.         (make-ir2-nlx-info
  242.          :home (when (member (cleanup-kind (nlx-info-cleanup nlx))
  243.                  '(:block :tagbody))
  244.              (make-normal-tn (backend-any-primitive-type *backend*)))
  245.          :save-sp (make-nlx-sp-tn env)))))
  246.   (undefined-value))
  247.